1305. Детская игра

Существует большое количество различных детских игр. В них легко играть, но придумывать подобные игры достаточно тяжело. Здесь мы обсудим одну из них. Каждому игроку даются n натуральных чисел. Он может из них составить большое число, склеивая имеющиеся числа друг с другом. Например, если имеются 4 числа 123, 124, 56, 90, то из них можно составить 1231245690, 1241235690, 5612312490, 9012312456, 9056124123 и так далее. Всего можно составить 24 больших числа. Но число 9056124123 будет наибольшим среди них.

Вам может показаться, что задачу решить просто. Но так ли просто справится с этой задачей ребенок, который только что узнал о существовании чисел?

Вход. Каждый тест начинается с натурального числа n (n ≤ 50). Следующая строка содержит n натуральных чисел. Последний тест содержит n = 0 и не обрабатывется.

Выход. Для каждого теста вывести в отдельной строке максимальное число, которое можно составить из имеющихся n натуральных чисел.

Пример входа	Пример выхода
4 123 124 56 90 5 123 124 56 90 9 5 9 9 9 9 9 0	9056124123 99056124123 99999

РЕШЕНИЕ

сортировка

Анализ алгоритма

Занесем входные числа в массив строк. Отсортируем строки согласно правилу: строка a меньше строки b тогда и только тогда, когда строка a + b меньше строки b + a (‘+’ – операция конкатенации строк). Строки сортируются по убыванию.

Пример

Рассмотрим первый тест. Последовательность обменов чисел при сортировке имеет вид:

123	127	1239	123127 < 127123
127	123	1239	1231239 < 1239123
127	1239	123	конец

Реализация алгоритма

В символьный массив m будем считывать очередное входное число, преобразовывать в тип string и заносить в s[i]. Все входные числа храним в массиве строк s.

char m[100];

string s[100];

Функция сравнения строк f имеет вид:

int f(string a, string b)

{

return a + b > b + a;

}

Основной цикл программы. Заносим входные слова в строковый массив s.

while(scanf("%d",&n),n)

{

for(i = 0; i < n; i++)

{

scanf("%s",m);

s[i] = string(m);

}

Сортируем строки согласно функции сортировки f.

sort(s,s+n,f);

Последовательно выводим отсортированные строки. Получим наибольшее число, которое можно получить из исходных в результате склейки.

for(i = 0; i < n; i++) printf("%s",s[i].c_str());

printf("\n");

}

Java реализация

import java.util.*;

// import java.io.*;

public class Main

{

public static class MyFun implements Comparator<String>

{

public int compare(String a, String b)

{

return (b+a).compareTo(a+b);

}

}

public static void main(String[] args) // throws IOException

{

//Scanner con = new Scanner(new FileReader("1305.in"));

Scanner con = new Scanner(System.in);

while(true)

{

int n = con.nextInt();

if (n == 0) break;

String s[] = new String[n];

for(int i = 0; i < n; i++) s[i] = con.next();

Arrays.sort(s, new MyFun());

for(int i = 0; i < n; i++) System.out.print(s[i]);

System.out.println();

}

con.close();

}

}